package com.fyl.basic_algorithm.dynamic_programming;

/**
 * @Description:
 * @author:fyl
 * @date 2021/4/19 16:51
 * @Modified By:
 * @Modified Date:
 */
public class MatrixDemo {
    private int minDist = Integer.MAX_VALUE;

    /**
     * 回溯算法实现矩阵最短路径
     * 调用方式minDistBT(0,0,0,w,n)
     *
     * @param i    行指针
     * @param j    列指针
     * @param dist 路径总长度
     * @param w    矩阵
     * @param n    矩阵的大小-1
     */
    public void minDistBT(int i, int j, int dist, int[][] w, int n) {
        if (i == n && j == n) {
            if (dist < minDist) minDist = dist;
            return;
        }

        if (i < n) {  //往下走，更新i=i+1, j=j
            minDistBT(i + 1, j, dist + w[i][j], w, n);
        }
        if (j < n) {  //往右走，更新i=i, j=j+1
            minDistBT(i, j + 1, dist + w[i][j], w, n);
        }
    }

    /**
     * 动态规划状态转移方程法解决矩阵问题
     * 调用方式minDist(n-1,n-1,matrix,mem)
     *
     * @param i      终点行
     * @param j      终点列
     * @param matrix 矩阵
     * @param mem    备忘录矩阵
     * @return 最短路径
     */
    public int minDist(int i, int j, int[][] matrix, int[][] mem) {
        if (i == 0 && j == 0) return matrix[0][0];
        if (mem[i][j] > 0) return mem[i][j];
        int minLeft = Integer.MAX_VALUE;
        if (j - 1 >= 0) {
            minLeft = minDist(i, j - 1, matrix, mem);
        }
        int minUp = Integer.MAX_VALUE;
        if (i - 1 >= 0) {
            minUp = minDist(i - 1, j, matrix, mem);
        }
        int currMinDist = matrix[i][j] + Math.min(minUp, minLeft);
        mem[i][j] = currMinDist;
        return currMinDist;
    }

    /**
     * 动态规划状态转移表法解决矩阵对端路径问题
     *
     * @param matrix 矩阵
     * @param n      矩阵大小
     * @return 最短路径
     */
    public int minDistDP(int[][] matrix, int n) {
        int[][] states = new int[n][n];
        int sum = 0;
        for (int i = 0; i < n; ++i) {  //初始化states的第一行数据
            sum += matrix[0][i];
            states[0][i] = sum;
        }
        sum = 0;
        for (int i = 0; i < n; ++i) {  //初始化states的第一列数据
            sum += matrix[i][0];
            states[i][0] = sum;
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < n; ++j) {
                states[i][j] = matrix[i][j] + Math.min(states[i][j - 1], states[i - 1][j]);
            }
        }
        return states[n - 1][n - 1];
    }
}

class Test {
    public static void main(String[] args) {
        MatrixDemo matrixDemo = new MatrixDemo();
        int[][] matrix = {{1, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};
        int n = 4;
        int[][] mem = new int[n][n];
        //动态规划状态转移方程
        int minDist = matrixDemo.minDist(n - 1, n - 1, matrix, mem);
        System.out.println("状态方程: " + minDist);
        matrixDemo.minDistBT(0, 0, 0, matrix, 3);
        int minDistDP = matrixDemo.minDistDP(matrix, n);
        System.out.println("状态表: " + minDistDP);
        System.out.println("回溯算法: " + minDist);


    }
}
